1. Field of the Invention
The present invention relates to a digital signal processor capable of performing an arithmetic processing of mainly a signal series.
2. Description of the Prior Art
FIG. 1 is a schematic block diagram of an arrangement of a first conventional digital signal processor which has been described in "A 50 nS FLOATING-POINT SIGNAL PROCESSOR VLSI", P. 401, ICASSP 86, 1986. It should be noted that for the sake of simplicity, only required blocks are illustrated in FIG. 1.
In FIG. 1, reference numeral 1 indicates an instruction memory for storing an instruction word; 2 denotes a program counter for outputting an address of the instruction memory 1 to an output path 51; 3 represents an instruction execution control unit for decoding the instruction word supplied from the instruction memory 1 via an output path 52, and for outputting a control signal via an output path 53 to the program counter 2, a calculation unit or the like; 4 is an internal data memory for storing calculation data; 5 represents a data bus for transferring data read out from the internal data memory 4 via the output path 54; 6a denotes a multiplier unit for performing multiplication on input data supplied from the data bus 5 via an output path 55; 7 indicates an accumulator for performing an accumulating operation; 8 represents an accumulating register for holding an accumulation result; and reference numeral 9 indicates a repeat counter for repeating the same instruction at plural times.
Furthermore, reference numeral 63 indicates an input/output path for connecting the repeat counter 9 and the data bus 5; 64 represents a selector for inputting the data which has been supplied via the output path 56 from the multiplier unit 6a, and the data which has been supplied from the data bus 5 via the output path 57 thereinto and for supplying output data via the output pth 58 to the accumulator 7; 65 denotes a selector for inputting the output data which has been supplied from the data bus 5 and the output data which has been supplied from the accumulating register 8 therein, and for supplying the output data via the output path 61 to the accumulator; and reference numeral 66 is an output path for transmitting a control signal of the repeat counter 9.
An operation of the above-described digital signal processor will now be described. In response to the address output from the program counter 2 via the output path 51, the instruction word read from the instruction memory 1 is inputted via the output path 52 to the instruction execution control unit 3. Based upon the decoded instruction, the instruction execution control unit 3 controls the operations by sending the control signal via the output path 53 to various sections.
The internal data memory 4 reads at most two pieces of data to the data bus 5 via the output path 54, and the multiplier 6a outputs the multiplication results with respect to two pieces of input data which has been supplied from the data bus 5 via the output path 55. The selector 64 selects either the output data which has been supplied from the multiplier 6a via the output path 56, or the output data which has been supplied from the data bus 5 via the output path 57. The selector 65 selects either the output data which has been supplied from the data bus 5 via the output path 59, or the output data which has been supplied from the accumulating register 8 via the output path 60.
The accumulator 7 adds the output data which has been supplied from the above-described selector 64 via the output path 58, to the output data which has been supplied from the selector 65 via the output path 61. The calculation result of the accumulator 7 is written via the output path 62 into the accumulating register 8.
It should be noted that the same instruction such as the above-described accumulation is carried out in such a manner that in accordance with the output data which has been supplied from the data bus 5 via the input/output path 63, the number preset in the repeat counter 9 can be repeated.
In accordance with the above-described arrangements, FIG. 3 shows a flowchart for explaining an operation in which a block which has a minimum distortion with respect to a block "A" of a certain data series, is detected among search blocks of m in number as shown in a data relationship diagram of FIG. 2.
An amount of distortion is calculated by equation 1: ##EQU1## where,
the block A is: x=(x.sub.1, x.sub.2. . . , x.sub.w)
the search blocks are: y.sub.k =(y.sub.k1,y.sub.k2, . . . , y.sub.kw) k=1.about.M
"M" and "W" are fixed integers.
That is to say, with respect to the output data of x.sub.h, y.sub.1h which have been read from the data memory 4 of the respective blocks, the accumulating calculations are performed by the number of the data (steps ST 11, ST 12), the distortion comparison is performed after M numbers of the respective block's distortions are obtained, and thereafter a minimum distortion and a block number thereof are obtained (step ST 13).
In this case, the digital signal processor having the arrangement shown in FIG. 1 requires both the comparison and update process by "M" times in order to perform a sum-of-product calculation within one machine cycle, where an amount of calculation becomes (W.times.M) times for the sum-of-product process, and furthermore M times for both the minimum distortion and the block number thereof are needed. As a result, a processing time required for the calculations becomes t.times.(M.times.W+M), where t is one machine cycle.
Since the conventional digital signal processor has been arranged with the above-described constructions, when, for instance, a block having a minimum distortion is detected among blocks having a certain data series and "M" pieces of search blocks, distortions for all of "M" pieces of blocks are calculated, these distortions are compared with each other, and then a block number (position) of a minimum distortion is detected. As a result, there are drawbacks that the number of calculations becomes very large and the required processing time is considerably long.
FIG. 5 is a schematic block diagram of the digital signal processing processor disclosed in "A 50 nS FLOATING-POINT SIGNAL PROCESSOR VLSI", P. 401, Proceedings of ICASSP 86, 1986. It should be noted that for the sake of simplicity, only necessary blocks are shown in FIG. 5.
In the block diagram of FIG. 5, reference numeral 1 denotes an instruction memory for storing an instruction word; 3 indicates an instruction execution control unit for controlling various operations of decoding the instruction word and calculations; 5 is a data bus for mutually connecting the following sections with each other and for mainly performing a data transmission; 4 is an internal data memory for storing the calculation data; 6 represents a calculating unit for performing various calculations with respect to two pieces of data which have been transferred from the data bus 5; 8 denotes an address generating unit capable of generating at most 3 addresses at the same time; 10A represents an external data memory connecting unit for controlling the read/write operations to an external data memory (not shown); 78 is an external address bus; 79 denotes an external data bus; 80 indicates an external device control signal bus; 81 is a serial port (referred to as an "SIO" hereinafter) for performing a serial data transmission between external devices (not shown in detail); and, reference numeral 82A denotes a direct data memory transfer control unit (referred to as a "DMAC" hereinafter) for controlling a direct data memory transfer (referred to as a "DMA" hereinafter) between SIO 81 and external data memory connecting unit 10A.
FIG. 6 illustrates a timing chart of external data memory accessing operations of the digital signal processor shown in FIG. 5. FIG. 6a is a read timing chart and FIG. 6b is a write timing chart. In FIGS. 6a and 6b, reference numeral 291 is an external address terminal; 292 represents a strobe signal for controlling the read timing supplied from the external data memory; 293 is an external data terminal; and, 294 represents a strobe signal for controlling write timing to the external data memory.
An operation of the digital signal processor will now be described. In FIG. 5, the instruction word of the designated address is read out from the instruction memory 1, and input via an input/output path 201 to the instruction execution control unit 3. The control signal and data which have been decoded by the instruction execution control unit 3 are transferred via an output path 202 to the data bus 5.
In response to this control signal, calculation data from the internal data memory 4 to the data bus 5 is read via an output path 203, the data from the data bus 5 is input via an output path 204 to the calculation unit 6, the calculating process and calculation result at the calculation unit 6 is output via an output path 205 to the data bus 5, the data sent from the data bus 5 to the internal data memory 4 is written via an output path 206, and various operations such as the external data memory access are controlled.
Both the address of the input data from the internal data memory 4 to the calculation unit 6 and the writing address of the output data from the calculation unit 6 to the internal data memory 4 are controlled by the address generating unit 8 having three systems of address generators. This address generating unit 8 generates the address with the readable/writable data input from the data bus 5 via an input/output path 210, controls the internal data memory 4 and the external data memory connection unit 10A in response to the data which has been outputted via output paths 208 and 209, and determines the input data and output data write destination to the calculation unit 6.
When, on the other hand, data is set to a specific register of DMAC 82A via the data bus 5 and a path (not shown), DMA is initialized.
Once DMA is initialized, all of operations other than the DMA transfer are interrupted, and the data transfer is carried out from SIO 81 to the external data memory connection unit 10A via the output path 208 and data bus 5. The transfer word number is set into the specific register of DMAC 82A in response to the instruction which has been previously outputted via the output path 201. As the settable transfer word numbers, a selection is made to only 64, 128, 256 and 512 words.
A description will now be made to FIG. 6. When the readout operation of the external data memory is carried out as shown in FIG. 6a, an RE terminal of the external device control signal bus 80 becomes active for 1 machine cycle, the strobe signal 292 informs the external device of the data readout, and the address data is output from the external address bus 78 for 1 machine cycle. Furthermore, the data read from the external device is fetched at the trailing edge of the same cycle.
When the writing operation of the external data memory as shown in FIG. 6b is carried out, a WE terminal of the external device control signal bus 80 becomes active for 1 machine cycle, the data writing operation is announced to the external device, the address data is output from the external address bus 78 and the write data is output from the external data bus 79 for one machine cycle.
Since the second conventional digital signal processor is arranged as described above, the following problems exist:
a). Since no direct data transfer is carried out between the internal data memory and external data memory, the processing efficiency of the internal calculation is lowered.
b). When the external data memory is accessed by way of the direct data transfer, the address of the external data memory is simple increasing sequence and the transfer word number cannot be arbitarily designated, so that it is difficult to directly transfer the two-dimensional block data.
c). Since the internal calculation of the processor is interrupted when the direct data transfer is carried out, the processing efficiency of the internal calculation is extremely lowered.
d). Since the external address output is fixed at 12 bits, the accessing region of the external data memory is narrow.
FIG. 7 is a schematic block diagram of the conventional digital signal processor (referred to as a "DSP" hereinafter) chip employed in the digital signal processor disclosed in IEEE, ICASSP 86, publications on page 401 "A 50 nS FLOATING-POINT SIGNAL PROCESSOR VLSI". It should be noted that for the sake of simplicity, only necessary blocks are illustrated in FIG. 7. In FIG. 7, reference numeral 1 indicates a program memory for storing a microprogram by which all of processes of DSP are performed; 3 indicates a control circuit for controlling the executions of various processes such as fetching and decoding of the microprogram of the program memory 1, reading of data, calculation, and writing of calculation results; 4 represents 2-port data memory capable of storing 2n bits (n is a positive integer) data as the data size, also of simultaneously reading two pieces of data, and also of writing one piece of data; 8 indicates an address generating unit for generating an address for the data memory 4; reference numerals 301 and 302 represent selectors; reference numeral 303 a multiplier circuit for performing a multiplication process and adding/subtracting process with respect to two pieces of data X and Y which are simultaneously read from the data memory 4 and supplied via the respective selectors 301 and 302; reference numeral 6 is a calculation unit for performing an arithmetic operation and accumulation with respect to the above-described two pieces of data or resultant data by the multiplier circuit 303, and, reference numeral 5 indicates a data bus for transferring both the above-described two pieces of data X and Y, and the resultant data by the calculation unit 6 between the calculation unit 6 and data memory 4.
An operation of the digital signal processor will now be described. First of all, an overall operation of the DSP shown in FIG. 7 will be described. That is, the address generating unit 8 generates the address with respect to the data memory 4 so as to supply to this data memory 4. Thereafter when the data is read out, two pieces of data are simultaneously read out from the data memory 4, and then supplied via the respective selectors 301 and 302 to the multiplier circuit 303 or calculation unit 6 as the data X and Y. At this time, the multiplier circuit 303 performs the multiplication process on these data X and Y, and also sum-of-product processes on the multiplication result, and finally supplies the resultant data to the calculation unit 6. Then, the calculation unit 6 perform such an arithmetic calculating process that summation, subtraction, and bit manipulation are executed to this resultant data or the above-described two pieces of data X and Y, and also supplies the resultant data to the data memory 4 via the data bus 5 for writing. The above-described series of processing operations are performed by a pipeline process in which the control circuit 3 reads the microprogram which has been stored in the program memory 1, the instruction is decoded by the control circuit 3, and the control signal 31 is output to the respective circuits.
Then, for the case where a sum-of-product calculation, a complex number calculation, and a binary three search vector quantizing calculation are executed in the DSP, descriptions of a required machine cycle number will now be made.
(1) A sum-of-product calculation.
FIG. 8 shows a calculation flow of a sum-of-product calculation. That is, at first, in a step ST 21, an initialization is executed. Namely, an address for the data memory 4 is set, and a loop number is set in the multiplier circuit 303 and calculation unit 6. Then, in a step ST 22, the sum-of-product calculation is performed in one machine cycle. In a next step ST 23, a decision process is made whether or not a count value of the repeat counter is equal to zero. In other words, a decision process whether or not the repeat calculations are executed M times which have been set in the previous initialization step, has been performed.
In this case, if the calculation result of the sum-of-product calculation output from the calculation unit 6 is assumed to be "Z", this "Z" will be expressed as follows: ##EQU2## It should be noted that input data series X and Y are defined by:
X=(x.sub.1, . . . , x.sub.n) , and
Y=(y.sub.1, . . . , y.sub.n).
Since two pieces of data read from the data memory 4, multiplication, and accumulation of the multiplied results are pipeline-processed, an amount of required calculations becomes M machine cycles per one output data when the loop numbers "M" are sufficiently great. Thus, this is the same in the case that the data size is equal to "n" bits.
(2). Complex number calculation.
FIG. 9 illustrates a calculation flow of a complex number calculation. That is to say, in a step ST 31, an initialization is carried out similar to the above-described step ST 21. In a subsequent step ST 32, and next step ST 33, a calculation on a real number part and a calculation on an imaginary number part are separately executed in two machine cycles respectively. In a next step ST 34, a decision is made whether or not the count value of the loop counter is equal to zero other words, a decision is made whether or not the calculations have been performed M times which have been set in the initialization.
In this case, if the input data X and Y are set to X=a.sub.1 +ja.sub.2, Y=b.sub.1 +jb.sub.2, respectively, a multiplication between these complex numbers X and Y is as follows: EQU X.times.Y=(a.sub.1 .times.b.sub.1 -a.sub.2 .times.b.sub.2) +j(a.sub.1 .times.b.sub.2 +a.sub.2 .times.b.sub.1) (3)
As a result, the calculations on the real number part and imaginary number part are executed in the two steps of ST 32 and ST 33. Accordingly, an amount of required calculation becomes five machine cycles per one output data.
(3). Binary tree search vector quantizing calculation.
FIG. 10 represents a calculation flow for explaining a binary tree search vector quantizing calculation. The function of this binary tree search is to perform a matching calculation between an input vector "x" and two output vectors "y.sub.0 " and "y.sub.1 at a certain search stage so as to detect an output vector containing a smaller matching distortion, and is to repeat such a matching calculation operation on two output vectors located at a stage below the detected vectors.
As in the above-described matching calculation, a vector inner product is utilized. Assuming that an element number of a vector is "k", a matching distortion quantity is defined as follows: ##EQU3## where
x=x.sub.1, . . . , x ,
y.sub.0 =y.sub.01, . . . , y.sub.0 ,
y.sub.1 =y.sub.11, . . . , y.sub.1 ,
As a consequence, at steps ST 42 and 43, "d.sub.0 " and "d.sub.1 " are calculated In the subsequent step ST 44, a comparison is made between "d.sub.0 " and "d.sub.1 ". Then the process is advanced to the subsequent process. Accordingly, an amount of required calculation per one stage is equal to (2k+5) machine cycles.
Since the third conventional digital signal processor is arranged as described above, even in case that the required data precision is enough of a half of a data size at its maximum, an amount of various calculations required is equal to that of the data precision with respect to the data size at its maximum. As a result, the calculation capabilities of the digital signal processor per se cannot be sufficiently utilized.
FIG. 11 is a schematic block diagram of the conventional digital signal processor (referred to as a "DSP" hereinafter) disclosed in, for instancee, "A 50nS FLOATING POINT SIGNAL PROCESSOR VLSI", on page 401, IEEE, ICASSP86. It should be noted that for the sake of simplicity, only necessary blocks are represented in FIG. 11.
In DSP shown in FIG. 11, reference numeral 1 indicates a program memory; 3 is a control circuit for controlling data transfer, calculation, branching and so on; 31 represents an output path for outputting a control signal from the control circuit 3; 404 indicates an output path from the control circuit 3 to the program memory 1; 405 is an output path from the program memory 1 to the control circuit 3; 4 denotes a data memory; 6 indicates a calculation unit including a multiplier, an arithmetic calculator, a shifter, an accumulator and so on; 5 is a data bus; 409 represents output paths from the data memory 4 to the data bus 5, and from the data bus 5 to the calculation unit 6; and, reference numeral 410 denotes output paths from the calculation unit 6 to the data bus 5 and from the data bus 5 to the data memory 4.
The operations of the DSP will now be described. The basic operations of DSP is controlled based upon the program read from the program memory 1, by the control circuit 3. Furthermore, the data read from the data memory 4 is subjected to a series of processing operations such as the instruction fetch, the decoding, data reading, calculation, and calculation result writing on inputting the data into the calculation unit 6.
When the same instruction is consecutively performed by way of the pipeline processing, one instruction may be approximately performed within one machine cycle. As a consequence, in case that a single instruction is repeatedly executed, the process speed may be increased more if the process is more consecutively executed.
However, if a specific condition is satisfied with the calculation results, the following branching process is required in the branching program. That is, in such a branching program, an intermediate check point is introduced in a routine, and the consecutive execution is once interrupted so as to judge a condition before the consecutive execution process is completed, and further a comparison is made between the calculation result data and the specific data. Thus, based upon the comparison result, the branching process is executed.
FIG. 12 is a process flow for performing an intermediate check while a series of consecutive execution is processed. The results of the calculation process is compared with a threshold value (steps ST 51 and 52). Thereafter, a decision is made whether or not an interrupt condition is satisfied (step ST 53). If YES, then this process is completed. If NO, another decision is made whether or not the final data is accomplished (step ST 54). If NO, then the process is returned to the previous step ST 51 in which the above-described operation is repeated. To the contrary, if YES, then this process is ended.
In a motion compensating process of an image encoding method, a difference absolute value accumulation is employed for a pattern matching so as to detect a minimum pattern. When, for instance, a value which is now accumulated exceeds a minimum value, the remaining accumulation is waste of time. In such a case, the process is advanced to the next routine for the sake of efficiency.
To this end, it is useful to perform the intermediate check to some extent. However, the various processes of comparisons and decisions, and also interruptions of the process accompany a loss of time. Further, according to the conventional DSP, it is possible to only judge the conditions on the positive or negative decision of the data. When a comparison of size is needed between the data and the specific threshold value, a subtraction is once carried out between the data in question and the threshold value, and thereafter, a decision can be performed based upon this subtraction result, resulting in a lower processing efficiency of DSP.
If there are a plurality of comparison threshold values, the processing efficiency is further lowered. For instance, in case that the process sorts are subdivided into plural numbers (n in number), the comparisons between the data in question and (n-1) threshold values, and the branching instructions based upon the comparison results are required. At least a loss of (n-1).times.2 machine cycles occurs.
Since the fourth conventional digital signal processor is so constructed, the processing efficiency is lowered because of the following reasons. That is, in case where the branching process is carried out depending upon the calculation results or intermediate calculation results, the process is interrupted during the consecutive processing steps, and subtractions and also comparison processes are executed.
FIG. 13 is a simplified schematic block diagram of a audio signal processor (DSSP1) which has been represented in Japanese Telecommunication Institute, symposium publication No. S10-1 in 1986. In the audio signal processor shown in FIG. 13, reference numeral 1 denotes an instruction memory into which instruction words have been stored; 3 represents an instruction execution control unit for controlling various operations such as decoding of the instruction word and calculations; and 2 indicates a program counter for holding an instruction address; 504 is a PC stack for preserving a return address used in the subroutine process and interruption process. This PC stack 504 preserves an instruction address 531 output from the program counter 2 just before the interruption process, until the process is accomplished. Reference numeral 505 indicates a sequence control unit for controlling the entire operation of the processor; 506 is a repeat control unit for performing a counting operation between the sequence control unit 505 and itself during the loop/repeat operation; 9 is a repeat counter for counting a repeat number during the execution of the repeat instruction; 508 is a program bus for transferring the decoded control data; 5 represents a data bus for transferring main data; 510 is a bus interface register for connecting the program bus and data bus 5; 4 represents a data memory for storing calculation data; 6 indicates a calculation processing circuit for performing arithmetic operations such as addition, subtraction, multiplication, and division; 513 is an interruption control unit for starting the interrupting process; 514 is an external interrupt request signal; and, reference numeral 515 denotes an external interrupt acknowledgement signal.
An operation of the DSSP1 will now be described. In general, a signal processor has a pipeline structure in order to increase a processing speed. For instance, in the signal processor as shown in FIG. 13, the structure thereof is 3-stage pipeline. Accordingly, the following description is made based upon the pipeline processing.
In a first stage of the pipeline, an instruction word 511 which is designated by an instruction address 531 output from the program counter 2 is read from the instruction memory 1 and then inputted into the instruction execution control unit 3.
In a second stage of the pipeline, both the control signal and data decoded by the instruction execution control unit 3 are transferred to the corresponding parts.
In a third stage of the pipeline, various operations are controlled. That is, the calculation data 512 are read from the data memory 4 to the data bus 5 in response to the control signal, and written from the data bus 5 into the data memory 4, and furthermore processed in the calculation unit 6.
The interruption control unit 513 has a 3-level interrupt function other than RESET. RESET not only resets the program counter 2, but also initializes control registers such as a status register (SR), a flag register (FR), an interruption, and a bus control.
An interrupt 0 (INTR0) is non-maskable, and the program counter 2 is set to an address "1" wheel an INTR0 signal is inputted.
An interrupt 1 (INTR1) is maskable, and is masked when RESET, INTR0, or INTR1 is accepted, or by being designated in the program. A release of masking is executed by the program. When this interruption is accepted, the program counter 2 is set to an address "2".
An interruption 2 (INTR2) is maskable, and corresponds to a normal interruption having an acknowledgement function.
When RESET, INTR0, INTR1, and INTR2 are accepted, or set by the program, INTR2 is masked. A release of masking is performed by the program. When an interruption request signal is accepted, an acknowledgement signal (INTR2) is outputted, and then an address "3" is set to the program counter 2.
An instruction word which will be executed after the normally executed instruction word, is stored in an address which is defined by adding 1 to the instruction address 531 where the normally executed instruction word has been stored.
In the first stage of the pipeline the instruction address 531 output from the program counter 2 is added by "+1" in the adder so as to produce an address defined by adding the instruction address 531 to "1".
In general, in the processor having a pipeline structure, a delay may be caused by this pipeline until the instruction has been executed. As shown in FIG. 14, in a machine cycle of time period Tn, the H/W interrupt request signal 514 is inputted into the interruption control unit 513.
In response to the above-described input, when the external interrupt acknowledgement signal 515 is outputted from the interrupt control unit 513, an instruction word designated by an instruction address PC(n) is read out. Since the interrupt signal has been received, the instruction word which has been stored in an "n" address of the instruction execution control unit 3 at the machine cycle of time period (Tn+1), is invalidated, and it is substituted by no operation instruction (nop).
The program counter 2 is set to an address "3" at the machine cycle of time period Tn, whereby an interruption process is performed. The process cannot be completely recovered from the interruption process because the executions of the instruction words designated by PC(n-1) and PC(n) have not yet accomplished, and operations of the program counter 2 and the various key registers are interrupted not preserved, before the interruption process is executed.
Since the conventional digital signal processor having the above-described pipeline structure is so arranged above, the correct data before the interruption cannot be guaranteed when the external interruption is executed while the normal instruction is performed. When the interruption is executed during the repeat operation, the remaining repeat instruction is not executed. This causes the process efficiency to be lowered in the image signal processing field where the external H/W interruption is executed, and a large quantity of data is processed at a high speed so as to obtain a correct calculation result.
FIG. 15 is an explanatory diagram of the conventional motion-compensation calculating method which is described in, for instance, "A METHOD OF INTERFRAME ENCODING BY EMPLOYING MOTION COMPENSATION/BACKGROUND PREDICTION", publication of Electronic Telecommunication Institute, 85/1 Vol. J68-B No. 1, pages 77 to 84 by H. KORODA: N. TAKEKAWA and H. HASHIMOTO. In particular, this diagram shows an entire search type method. In FIG. 15, reference numeral 603 indicates a presently input block having a block size of l.sub.1 .times.l.sub.2 used for compensating a motion of a position in the present input frame; and 604 indicates a motion vector search range for representing a range of (l.sub.1 +2m) and (l.sub.2 +2n) where a block is located. This block is matching-processed with the present input block 603 in the previous input frame.
In this case, the number "M" of the search blocks is expressed by: EQU M=(2m+1).times.(2n+1) (6)
The search range is defined by a range of -m to +m pixels in the horizontal direction and a range of -n to +n pixels in the vertical direction.
The motion compensation is executed at a predetermined sized block unit by obtaining a prediction signal approximate to the present input frame data while utilizing an inter-frame correlation between the present input frame data and previous input frame data in the inter-frame encoding transmission method. Then, a block having a minimum inter-block-distortion quantity against a present input block 603 within a present input frame data, is searched among the motion vector search range 604 within the previous input frame data to obtain a motion vector and a prediction signal. This block corresponds to a block having the highest correlation with the present input block 603 with a calculation method such as a sum-of-absolute-difference calculation.
FIG. 16 is a schematic block diagram of an image encoding transmission apparatus where a general inter-frame encoding process is performed. Ill FIG. 16, reference numeral 601 denotes an input signal of image data constructed of a plurality of sequential frames in a time series; 602 denotes a motion compensation unit for obtaining a prediction signal by calculating approximation of a correlation between a present input block 603 of the input signal 601 and a motion vector search range 604 given as a previous input signal 601; reference numerals 605 and 606 are prediction signals outputted from the motion compensation unit 602; 607 is a encoding unit for encoding a difference signal between the input signal 601 and prediction signal 606 so as to output a motion compensated signal; 608 denotes a decoding unit for decoding the motion compensated signal which has been encoded in the encoding unit 607; and, reference numeral 609 indicates a frame memory for adding the signal from the decoding unit 607 to the prediction signal 606 from the motion compensation unit 602 so as to obtain reproduced data to De stored therein, and also for giving the motion vector search range 604 to the motion compensation unit 602.
In the image encoding transmission apparatus with the above-described arrangement, operation thereof will now be described with reference to an explanatory diagram of FIG. 17.
The configuration shown in FIG. 16 has functions as follows: each of inter-block distortions between the present input block "x" 603 with a size of l.sub.1 .times.l.sub.2 at a specific position within the present input frame and the respective blocks of M in number within the motion vector search range 604 of the previous input frame, is calculated; and a minimum value of these distortions, i.e., a relative position of a minimum distortion block "y" indicated by the minimum distortion, with respect to the position of the present input block 603, is searched as a motion vector; so that a signal "ymin" of this block is output as a generated prediction signal 605. Then, in the frame inter-frame encoding transmission, the prediction signal can be produced even at the reception side by transmitting the motion vector information at the reception side.
Assuming now that the number of the motion vectors "V" to be searched within a given motion vector search range 604 is "M" (an integer not less than 2). In the case where a sum-of-absolute-differences is employed as a distortion quantity between the previous frame block at the position of the specific motion vector "V" and the presently input block, an amount of distortion is calculated by: ##EQU4##
It should be noted that the input block is x=(x.sub.1, x.sub.2, . . . , xL), the block to be searched is yi=(yi1, yi2, . . . , yiL), and i=1 to M, L is equal to l.sub.1 .times.l.sub.2. Thus, the motion vector V is obtained by: EQU V=Vi(min di .vertline.i=1.about.M) (8)
Then, a calculation amount S1 of this case is obtained by the following equation when the sum-of-absolute-differences calculation needs "a" machine cycles and the comparison process needs "b" machine cycles. EQU S1=L.times.M.times.a+M.times.b (9)
In case that, for instance, a=1 machine cycle, b=2 machine cycles, l.sub.1 =8, l.sub.2 =8, m=8, and n=8, then L=64, M=289, and; EQU S1 19,000 (10)
machine cycles. This is very large value in view of the hardware arrangement. The high-speed calculation system such as the pipeline processing has been used in accordance with the frame cycle of the image signal.
However, it is a great problem to reduce the quantity of the hardware. In accordance with Japanese KOKAI (Laid-open) patent application No. 63-181585, for instance, entitled: "AN APPARATUS FOR MOTION COMPENSATION INTER-FRAME ENCODING OF A TV SIGNAL", it has been proposed a method for calculating a tree search type motion compensation so as to reduce an amount of calculations. FIG. 18 is an illustration for explaining a method of a motion compensation calculation. There are arranged first blocks ".largecircle." of low density at equal intervals to be searched within the motion vector search range 604. When a block ".largecircle." giving the minimum distortion is detected, second blocks ".quadrature." to be searched are positioned within a narrow region with this block ".largecircle." as a center thereof. In this narrow region, a block ".quadrature." giving the minimum distortion is detected. Furthermore, third blocks ".increment." to be searched are set within another region with this block ".quadrature." as a center thereof so as to detect a block ".increment." giving the minimum distortion. Finally, the block ".increment." giving the minimum distortion within the motion vector search range 604 is specified.
An amount of the calculations "S2" in this case is expressed by: EQU S2=(9.times.L.times.a+9.times.b).times.3 (11).
As a result, under the same conditions as the above, it becomes EQU S=1,800 (12)
machine cycles.
Although the quantity of calculation according to this tree search type motion compensation calculating method becomes small, the capability to detect the minimum distortion block is lowered as compared with that of the full search type motion compensation calculating method. That is to say, there are considerable possibilities that at the matching process of the first search operation with the low density, a selection is made of a block of which is positioned is apart from that of the correct block having the minimum distortion. As a consequence, there are many cases where the calculation result cannot reach the expected minimum distortion amount and gives a decision of no correlation, resulting in a lower efficiency.
Since the conventional motion compensation calculating method has been so arranged as above, a calculation amount becomes great if the full searching operation with high reliability in the motion compensation calculating is employed, so that a large scale arrangement of hardware is required. On the other hand, if the calculation amount is reduced by way of the tree searching method, the detectability of the minimum distortion block is lowered. As a consequence, there are problems of the erroneous detections and insufficient efficiency.